package Demo89;

import java.util.*;

/**
 * 单词接龙
 * https://leetcode.cn/problems/om3reC/
 */
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> vis = new HashSet<>();
        HashSet<String> hash = new HashSet<>();
        for( String str : wordList) {
            hash.add(str);
        }
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        // 处理边界情况
        if(beginWord.equals(endWord)) return 0;
        if(!wordList.contains(endWord)) return 0;
        int ret = 1;
        while(!q.isEmpty()) {
            ret++;
            int sz = q.size();
            while(sz-- != 0) {
                String t = q.poll();
                for(int i = 0; i < beginWord.length(); i++) {
                    char[] tmp = t.toCharArray();
                    for(int j = 0; j < 26; j++) {
                        tmp[i] = (char)(j + 'a');
                        String next = new String(tmp);
                        if(hash.contains(next) && !vis.contains(next)) {
                            if(next.equals(endWord)) return ret;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        int ret = solution.ladderLength("a", "c", list);
        System.out.println(ret);
    }
}